import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BarrelSort {
    public static void main(String[] args) {
        int[] arr = {1,88,9,2,0,8,95,0};
        BarrelSort barrelSort = new BarrelSort();
        barrelSort.BaseSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    public void BaseSort(int[] arr) {
        //先找最大数，确保最大的数据有几位
        int Redix = findMax(arr);

        //创建一个链表数组
        LinkedList<Integer>[] linkedLists = new LinkedList[10];

        //一定记得初始每个数组
        for (int i = 0; i < linkedLists.length; i++) {
            linkedLists[i] = new LinkedList<>();
        }

        for (int r = 1; r <= Redix; r++) {
            for (int i = 0; i < arr.length; i++) {
                //每一次都求末位并递推
                linkedLists[getIndex(arr[i], r)].offer(arr[i]);
            }

            //此时已经相当于完成了一次排序
            int index = 0;
            //直接按照队列出队并复制到原数组
            for (int i = 0; i < linkedLists.length; i++) {
                while (!linkedLists[i].isEmpty()) {
                    arr[index++] = linkedLists[i].poll();
                }
            }
        }
    }

    public int getIndex(int n, int r) {
        int ret = 0;
        for (int i = 1; i <= r; i++) {
            ret = n % 10;
            n /= 10;
        }
        //此时就得到想要的末位
        return ret;
    }

    public int findMax(int[] arr) {
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return (max + "").length();//相当于转换为字符串求位数
    }

    public static void barrelSort(int[] nums) {
        int n = nums.length;
        int max = 0, min = 0;

        //找出最大最小值
        for (int i = 0; i < n; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            if (nums[i] < min) {
                min = nums[i];
            }
        }

        int size = (max - min) / n + 1;//获取桶的个数，至少保证有一个
        int count = (max - min) / size + 1;//得知每个桶中存取数据范围

        List<Integer>[] barrel = new List[count];//初始化每个桶
        for (int i = 0; i < count; i++) {
            barrel[i] = new ArrayList<>();
        }

        //扫描一遍数组，把数放在对应的桶里面
        for (int i = 0; i < n; i++) {
            int index = (nums[i] - min) / size;//定位第几个桶
            barrel[index].add(nums[i]);
        }

        //对同种每个数据进行排序，这里使用快排
        for (int i = 0; i < count; i++) {
            barrel[i].sort(null);//默认就是升序排序，不需要使用比较器
        }

        //一次出桶
        int index = 0;
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < barrel[i].size(); j++) {
                nums[index++] = barrel[i].get(j);
            }
        }

    }
    public static void main1(String[] args) {
        int[] nums = {2,2,2,2,2,1,2,3};
        barrelSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }

    }
}
